package 回溯;

import java.util.*;

/**
 * @author admin
 * @version 1.0.0
 * @ClassName 组合总和.java
 * @Description TODO
 * @createTime 2020年11月01日 17:22:00
 * 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 *
 * candidates 中的数字可以无限制重复被选取。
 *
 * 说明：
 *
 * 所有数字（包括 target）都是正整数。
 * 解集不能包含重复的组合。 
 * 示例 1：
 *
 * 输入：candidates = [2,3,6,7], target = 7,
 * 所求解集为：
 * [
 *   [7],
 *   [2,2,3]
 * ]
 *
 * 主要是怎么减枝
 * 每一次搜索的时候设置 下一轮搜索的起点 begin
 * 就是规定可以无限次使用同一个数 但只能同时使用这个数 比如2 2 3 可以的2 3 2是不可以的这样就保留 了一个使其不会重复
 * 具体做法就是函数中传一个参数进去 每次只能从当前这个参数使用
 */
public class 组合总和 {
    class Solution {
        List<List<Integer>> res=new ArrayList<>();
        public List<List<Integer>> combinationSum(int[] nums, int target) {
            Deque<Integer> track=new ArrayDeque<>();
            int count=0;
            Arrays.sort(nums);
            back(nums,count,track,target,0);
            return res;
        }

        void back(int[] nums, int count, Deque<Integer> track, int target, int begin){
            if(count>target){
                return;
            }
            if(target==count){
                res.add(new ArrayList<>(track));
                return ;
            }
            for(int i=begin;i<nums.length;i++){

                count+=nums[i];

                track.add(nums[i]);
                back(nums,count,track,target,i);
                track.removeLast();
                count-=nums[i];
            }

        }
    }



}
